package com.jake.data_structure_learning.days;

import java.util.ArrayList;
import java.util.List;

/**
 * copyright (C), 2021, 武汉德辞信息技术有限公司
 *
 * @author WangXiang
 * @version 1.0.0
 * @create 2021/5/18 16:58
 * @description <author>                <time>                  <version>
 * WangXiang               2021/5/18 16:58            1.0.0
 */
public class Day_20200518 {
    /**
     * 将有序数组转换为二叉搜索树
     * 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
     * <p>
     * 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
     * <p>
     *  
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：nums = [-10,-3,0,5,9]
     * 输出：[0,-3,9,-10,null,5]
     * 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
     * <p>
     * 示例 2：
     * <p>
     * <p>
     * 输入：nums = [1,3]
     * 输出：[3,1]
     * 解释：[1,3] 和 [3,1] 都是高度平衡二叉搜索树。
     *  
     * <p>
     * 提示：
     * <p>
     * 1 <= nums.length <= 104
     * -104 <= nums[i] <= 104
     * nums 按 严格递增 顺序排列
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return sortedArrayToBST(nums, 0, nums.length - 1);
    }

    public TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }

        int mid = (start + end) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, start, mid - 1);
        root.right = sortedArrayToBST(nums, mid + 1, end);
        return root;
    }


    /**
     * 二叉搜索树中的众数
     *
     * @param root
     * @return
     */
    private int currentVal;
    private int currentNums;
    private int maxNums;
    private List<Integer> results = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        // 中序遍历 是有序的数字
        if (root == null) {
            return null;
        }
        this.midOrder(root);
        int[] nums = new int[results.size()];
        for (int i = 0; i < results.size(); i++) {
            nums[i] = results.get(i);
        }
        return nums;
    }

    public void midOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        this.midOrder(node.left);
        System.out.println(node.val);
        if (node.val == currentVal) {
            currentNums++;
        } else {
            currentVal = node.val;
        }

        if (currentNums > maxNums) {
            results.clear();
            results.add(node.val);
            maxNums = currentNums;
        } else if (currentNums == maxNums) {
            results.add(node.val);
        }

        this.midOrder(node.right);
    }

//    public boolean isBalance(TreeNode node) {
//        if (node == null) {
//            return true;
//        }
//
//
//    }
//
//    public int maxDepth(TreeNode node) {
//        if (node == null) {
//            return 0;
//        }
//
//    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}


